#include <QtGui>
#include <iostream>

#include <string>
#include <fstream>
#include <iostream>
#include <sstream>
#include <stdio.h>
#include <stdlib.h>
#include <map>
#include <time.h>

#include "image_utils.cpp"
#include "nodo.h"
#include "solucion.h"
#include "busqueda.h"

using namespace std;
using namespace Qt;
using namespace ImageUtils;

Busqueda::Busqueda(QWidget *parent)
  : QDialog(parent)
{
  setupUi(this);

  connect(pushButton_img, SIGNAL(clicked()), this,SLOT(Mostrar()));

  connect(pushButton_buscar, SIGNAL(clicked()), this,SLOT(Buscar()));

}

void Busqueda::Mostrar(){
  const char * format = 0;
  ImageConversionFlags flags = AutoColor;
  QGraphicsScene * scene = new QGraphicsScene;
  QString image_in = lineEdit_img->text();
  QPixmap pixmap(image_in, format, flags);
  scene->addPixmap(pixmap.scaled(700,719,IgnoreAspectRatio,FastTransformation));
  graphicsView->setScene(scene);
  graphicsView->show();
}

//ALGORITMOS DE BÚSQUEDA//
float F_Anchura(Nodo &nodo_aux, int *posFin){
  return nodo_aux.get_prof();
}
float F_CosteU(Nodo &nodo_aux, int *posFin){
    return nodo_aux.get_cost();
}
float F_Prof(Nodo &nodo_aux, int *posFin){
  return -(nodo_aux.get_prof());
}
float F_Euclidea(Nodo &nodo_aux, int *posFin){
  float dist, cost;
  dist = sqrt(pow((posFin[0] - nodo_aux.get_coX()),2) +
	      pow((posFin[1] - nodo_aux.get_coY()),2));
  cost = nodo_aux.get_cost() + dist;
  return cost;
}
float F_Manhattan(Nodo &nodo_aux, int *posFin){
  float dist, cost;
  dist = abs(posFin[0] - nodo_aux.get_coX()) +
         abs(posFin[1] - nodo_aux.get_coY());
  cost = nodo_aux.get_cost() + dist;
  return cost;
}
///////////////////////

void Crear_Solucion(Solucion &sol, Nodo &nodo){
  sol.set_cost(nodo.get_cost());
  Nodo* nodo_aux = &nodo;
  while(nodo_aux->get_father() != NULL){
    sol.set_posicion(make_pair(nodo_aux->get_coX(),nodo_aux->get_coY()));
    nodo_aux = nodo_aux->get_father();
  }
  sol.set_posicion(make_pair(nodo_aux->get_coX(),nodo_aux->get_coY()));
}

bool Expandir(int **mapa_aux, int **mapa,
	      int X, int Y, int *max_dimension,
	      Nodo &nodo_actual, multimap<int,Nodo*> &frontera,
	      multimap<int,Nodo*> &visitados, int *pos_fin,
	      int estrategia){
  bool expandido = false;
  float(*p_func)(Nodo&, int*);
  float f=0;
  int posicion = 0;

  switch(estrategia){
  case 1: //anchura
    p_func = F_Anchura;
    break;
  case 2: //coste uniforme
    p_func = F_CosteU;
    break;
  case 3: //profundidad
    p_func = F_Prof;
    break;
  case 4: //profundidad acotada
    p_func = F_Prof;
    break;
  case 5: //profundidad iterativa
    p_func = F_Prof;
    break;
  case 6: //A* Euclídea
    p_func = F_Euclidea;
    break;
  case 7: //A* Manhattan
    p_func = F_Manhattan;
    break;
  default:
    cout << "Opcion incorrecta en P_FUNC!!!!" << endl;
    return false;
  } //end case estrategia-funcion

  int aux_coste;
  if (X >= 0 && X <= max_dimension[0] &&
      Y >= 0 && Y <= max_dimension[1]){
    if (mapa[X][Y]==0)
      aux_coste = 100;
    else
      aux_coste = mapa[X][Y];

    Nodo * aux_nodo = new Nodo(0,0,0,0,NULL,0);
    aux_nodo->set(X,Y,aux_coste,&nodo_actual);
    f = p_func(*aux_nodo, pos_fin);
    posicion = X+(Y*(pos_fin[0]+1));
    if (mapa_aux[X][Y]>=0){
      aux_nodo->set_f(f);
      frontera.insert(pair<int,Nodo*>(aux_nodo->get_f(),aux_nodo));
      mapa_aux[X][Y] = -1;
      visitados.insert(pair<int,Nodo*>(posicion,aux_nodo));
      expandido = true;
    }
    else{
      if(mapa_aux[X][Y]==-1){//visitados
	Nodo* nodo_ant = visitados.find(posicion)->second;
	if (aux_nodo->get_cost() < nodo_ant->get_cost()){
	  aux_nodo->set_f(f);
	  frontera.insert(pair<int,Nodo*>(aux_nodo->get_f(),aux_nodo));
	  visitados.insert(pair<int,Nodo*>(posicion,aux_nodo));
	  expandido = true;
	}
      }
    }
  }//end if dentro márgenes
  return expandido;
} //end Expandir

Solucion Buscar_sol(int **mapa, int *pos_ini, int *pos_fin, int *max_dimension, int estrategia){
  Solucion sol;
  int i,X,Y;
  int nodos_cont = 0;
  Nodo inicial(pos_ini[0],pos_ini[1],0,0,NULL,0);
  multimap<int,Nodo*> frontera;
  multimap<int,Nodo*> visitados;
  int** mapa_aux = new int*[max_dimension[0]+1];
  for (i = 0; i <max_dimension[0]+1; i++) {
    mapa_aux[i] = new int[max_dimension[1]+1];
  }
  int dep,wid;
  for(dep=0;dep<max_dimension[1]+1;dep++){

    for(wid=0;wid<max_dimension[0]+1;wid++){
      //memcpy(mapa_aux[wid], mapa[wid], sizeof(mapa_aux[wid]));
      mapa_aux[wid][dep] = mapa[wid][dep];
    }
  }

  frontera.insert(pair<float,Nodo*>(inicial.get_f(), &inicial));
  visitados.insert(pair<int,Nodo*>(0, &inicial));

  while (!frontera.empty()) {
    Nodo* nodo_actual = frontera.begin()->second;
    frontera.erase(frontera.begin());
    if(nodo_actual->esSolucion(pos_fin)){
      Crear_Solucion(sol,*nodo_actual);
      break;
    }
    else{
      X = nodo_actual->get_coX();
      Y = nodo_actual->get_coY();
      /* expandimos  DCHA-ABAJO-IZQ-ARRIBA */
      if(Expandir(mapa_aux,mapa,X+1,Y,max_dimension,*nodo_actual,frontera,
		  visitados,pos_fin,estrategia))
	nodos_cont ++;
	 if(Expandir(mapa_aux,mapa,X,Y+1,max_dimension,*nodo_actual,frontera,
		     visitados,pos_fin,estrategia))
	nodos_cont ++;
	 if(Expandir(mapa_aux,mapa,X-1,Y,max_dimension,*nodo_actual,frontera,
		     visitados,pos_fin,estrategia))
	   nodos_cont ++;
	 if(Expandir(mapa_aux,mapa,X,Y-1,max_dimension,*nodo_actual,frontera,
		     visitados,pos_fin,estrategia))
	   nodos_cont ++;
	 }
    }//end while frontera no vacía
  //sol.toString();
  cout << "Total nodos expandidos: " << nodos_cont<<endl;
  return sol;
}

void Rellenar_Mapa(Solucion s1, int **mapa){
  while(!s1.empty_posiciones()){
    mapa[s1.get_posicion().first][s1.get_posicion().second] = 15;
    s1.pop_posicion();
  }
}

Solucion Vecina(Solucion sol_orig, int **mapa){
  Solucion sol_ret;
  Solucion sol_aux;
  int rand1,rand2;
  sol_ret.set_cost(COST_MAX);

  rand1 = (rand()%(sol_orig.size_posiciones()/2 -1))+1;// entre 1 y número de nodos de la solución /2
  rand2 = (rand()%(sol_orig.size_posiciones()/2 -1))+sol_orig.size_posiciones()/2;// segunda mitad

  // unión Bresenham*
  sol_aux = sol_orig.vecina2(rand1, rand2, mapa);
  if(sol_aux.get_cost() < sol_ret.get_cost()){
    sol_ret.copiar(sol_aux);
  }

  // unión angulo izq
  sol_aux = sol_orig.vecina3(rand1, rand2, mapa);
  if(sol_aux.get_cost() < sol_ret.get_cost()){
    sol_ret.copiar(sol_aux);
  }

  // unión angulo dcho
  sol_aux = sol_orig.vecina4(rand1, rand2, mapa);
  if(sol_aux.get_cost() < sol_ret.get_cost()){
    sol_ret.copiar(sol_aux);
  }

  rand1 = (rand()%(sol_orig.size_posiciones()/4 -1))+1;// entre 1 y número de nodos de la solución /4
  rand2 = (rand()%(sol_orig.size_posiciones()/4 -1))+sol_orig.size_posiciones()/4;// segundo cuarto
  //segunda vuelta mas fina, primera mitad
  sol_aux = sol_ret.vecina2(rand1/2, rand1-1, mapa);
  if(sol_aux.get_cost() < sol_ret.get_cost()){
    sol_ret.copiar(sol_aux);
  }
  sol_aux = sol_ret.vecina3(rand1/2, rand1-1, mapa);
  if(sol_aux.get_cost() < sol_ret.get_cost()){
    sol_ret.copiar(sol_aux);
  }
  sol_aux = sol_ret.vecina4(rand1/2, rand1-1, mapa);
  if(sol_aux.get_cost() < sol_ret.get_cost()){
    sol_ret.copiar(sol_aux);
  }

  rand1 = (rand()%(sol_orig.size_posiciones()/4 -1))*2+1;
  rand2 = (rand()%(sol_orig.size_posiciones()/4 -1))*2+sol_orig.size_posiciones()/4;
   //tercra vuelta mas fina, segunda mitad
  sol_aux = sol_ret.vecina2(rand2/2, rand2-1, mapa);
  if(sol_aux.get_cost() < sol_ret.get_cost()){
    sol_ret.copiar(sol_aux);
  }
  sol_aux = sol_ret.vecina3(rand2/2, rand2-1, mapa);
  if(sol_aux.get_cost() < sol_ret.get_cost()){
    sol_ret.copiar(sol_aux);
  }
  sol_aux = sol_ret.vecina4(rand2/2, rand2-1, mapa);
  if(sol_aux.get_cost() < sol_ret.get_cost()){
    sol_ret.copiar(sol_aux);
  }


  return sol_ret;
}

void Templar(int &temp, int index, int diff){
  if(diff!=0)
    temp = temp  - index/diff;//10;
}


Solucion Vecina2(Solucion sol_orig, int **mapa, int *pos_fin, int *max_dimension){
  Solucion sol_2;
  int pos_corte = rand()%(sol_orig.size_posiciones()-10) + 4;// entre 1 y número de nodos de la solución
  int estrategia = rand()%6 +2; //estrategias entre 2 y 7
  pair<int,int> pos_m1;
  int* pos_mod = new int[2];
  pos_m1=sol_orig.cortar(pos_corte, mapa);
  pos_mod[0]= pos_m1.first;
  pos_mod[1]= pos_m1.second;

  sol_2 = Buscar_sol(mapa, pos_mod, pos_fin, max_dimension,estrategia);

  sol_orig.concatenar_sol(sol_2.get_Pposiciones());
  return sol_orig;
}

void Busqueda::Buscar(){
  int i, itera, width, depth, diff, estrategia=0;
  int temp = 100;
  Solucion s1, aux_sol;
  QString image_in = lineEdit_img->text();
  clock_t t_time;

  if (radioButton_1->isChecked())
    estrategia = 1; // cout << "Anchura"         << endl;
  if (radioButton_2->isChecked())
    estrategia = 2; // cout << "Coste Uniforme"  << endl;
  if (radioButton_3->isChecked())
    estrategia = 3; // cout << "Profundidad"     << endl;
  if (radioButton_4->isChecked())
    estrategia = 4; // cout << "Prof. acotada"   << endl;
  if (radioButton_5->isChecked())
    estrategia = 5; // cout << "Prof. iterativa" << endl;
  if (radioButton_6->isChecked())
    estrategia = 6; // cout << "A* Euclidea"     << endl;
  if (radioButton_7->isChecked())
    estrategia = 7; // cout << "A* Manhattan"    << endl;
  if (radioButton_8->isChecked())
    estrategia = 8; // cout << "Ascenso de colinas"    << endl;
  if (radioButton_9->isChecked())
    estrategia = 9; // cout << "Temple simulado"    << endl;

  string aux_image_in = image_in.toStdString();
  BasicImageUtils::ImageDimensions((char*)aux_image_in.c_str(),width,depth);
  int** mapa = new int*[width];
  for (i = 0; i < width; i++) {
    mapa[i] = new int[depth];
  }

  BasicImageUtils::Map((char*)aux_image_in.c_str(),mapa);
  int* pos_ini = new int[2];
  pos_ini[0] = 0;
  pos_ini[1] = 0;
  int* pos_fin = new int[2];
  pos_fin[0] = width-1;
  pos_fin[1] = depth-1;
  int* max_dimension = new int[2];
  max_dimension[0] = width-1;
  max_dimension[1] = depth-1;

  bool cont_vec = true;

  t_time = clock();
  if (estrategia<8){
    s1 = Buscar_sol(mapa,pos_ini,pos_fin, max_dimension, estrategia);
    s1.toString();

    t_time = clock()-t_time;
    cout <<"Time: " << (float)t_time/CLOCKS_PER_SEC << endl;

    Rellenar_Mapa(s1, mapa);
    cout <<"Guardando Mapa" << endl;
    BasicImageUtils::PrintMap(mapa,(char*)"sol.pgm", width, depth);
  }
  else{
    s1 = Buscar_sol(mapa,pos_ini,pos_fin, max_dimension, 3); //empezamos en profundidad

    if (estrategia==8){//ascenso de colinas
      itera = 0;
      for(i=0;i<5;i++){
	cont_vec = true;
      while(cont_vec){
	itera++;
	aux_sol=Vecina(s1, mapa);
	// //comparar
	// cout << "          s1: ";
	// s1.toString();
	// cout << "          aux_sol: ";
	// aux_sol.toString();
	cout << itera << " ";
	aux_sol.P4plot_coste();
	if(aux_sol.get_cost() < s1.get_cost()){
	  s1.copiar(aux_sol);
	}
	else
	  cont_vec = false;
      }
      }
      //      cout <<"Número total de iteraciones: " <<itera<<endl;
    }

    if(estrategia==9){//temple simulado
      itera = 0;
      while(temp> 0){
    	aux_sol=Vecina(s1, mapa);
	// //comparar
	// cout << "          s1: ";
	// s1.toString();
	// cout << "          aux_sol: ";
	// aux_sol.toString();
	cout << itera << " ";
	aux_sol.P4plot_coste();
	diff = abs(s1.get_cost()-aux_sol.get_cost());
 	if (rand()%100 > pow(M_E,(-diff/temp))){
    	  if(aux_sol.get_cost() < s1.get_cost())
    	    s1.copiar(aux_sol);
    	}
    	Templar(temp, itera, diff); //g(T)
	itera++;
      }
      cout <<"Número total de iteraciones: " <<itera <<endl;
    }
    // cout<< "   Sol Final:"<<endl;
    s1.toString();
    t_time = clock()-t_time;
    // cout <<"Time: " << (float)t_time/CLOCKS_PER_SEC << endl;
    Rellenar_Mapa(s1, mapa);
    cout <<"Guardando Mapa" << endl;
    BasicImageUtils::PrintMap(mapa,(char*)"sol.pgm", width, depth);
  }


  QGraphicsScene * scene = new QGraphicsScene;
  QPixmap pixmap("sol.pgm");
  scene->addPixmap(pixmap.scaled(700,719,IgnoreAspectRatio,FastTransformation));
  graphicsView->setScene(scene);
  graphicsView->show();

  cout << "Done" << endl;

}
